package JzOffer.jz48;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 张取
 * @version 1.0
 * @date 2022/1/22 下午5:02
 * JzOffer.jz48
 */

public class Codec02 {
    //层次遍历实现
    public String serialize(TreeNode root){
        StringBuilder res = new StringBuilder();
        //层次遍历辅助队列
        //Queue<TreeNode> queue = new ArrayDeque<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return "";
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode curNode = queue.poll();
            //非空节点
            if(curNode != null){
                res.append(String.valueOf(curNode.val));
                //先将左右子树入队，等其出队(遍历到时)时再判断
                queue.offer(curNode.left);
                queue.offer(curNode.right);
            } else { //空节点
                res.append("null");
            }
            res.append(","); //添加节点区分分割符
        }
        return res.toString();
    }

    public TreeNode deserialize(String data){
        if(data == ""){
            return null;
        }
        String[] nodeList = data.split(",");
        //创建根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodeList[0]));
        //层次遍历辅助队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int idx = 1; //用于遍历节点列表
        while(!queue.isEmpty()){
            TreeNode curNode = queue.poll();
            //创建左子树
            if(!nodeList[idx].equals("null")){
                curNode.left = new TreeNode(Integer.valueOf(nodeList[idx]));
                queue.offer(curNode.left);
            }
            idx++;
            //创建右子树
            if(!"null".equals(nodeList[idx])){
                curNode.right = new TreeNode(Integer.parseInt(nodeList[idx]));
                queue.offer(curNode.right);
            }
            ++idx;
        }
        return root;
    }
}
